package 单向循环链表;

import javax.swing.*;

public class TestDemo {
    public static void main(String[] args) {
        SCll list = new SCll();
        list.addNode(5);

        list.josephus(3);
    }
}

/*
* 单向循环链表解决约瑟夫问题
* 约瑟夫问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，
* 数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，
* 由此产生一个出队编号的序列。
 * */

class SCll{
    // 创建一个头节点,当前没有编号
    Boy First = null;


    public void josephus(int m){
        // 如果First为空或者First.next = First,直接出First
        if(First == null){
            System.out.println("空!");
            return;
        }
        if(First.next == First){
            System.out.println(First.no+" -> "+null);
            return;
        }


        Boy cur = First;
        // 找尾
        while(cur.next != First){
            cur = cur.next;
        }

        //遍历取元素
        while(true){
            // 取到最后一个元素了
            if(cur.next == cur){
                System.out.println(cur.next.no+" -> "+ null);
                break;
            }

            int count = 0;

            while(count < m-1){
                cur = cur.next;
                count++;
            }
            System.out.print(cur.next.no+" -> ");
            cur.next = cur.next.next;
            cur = cur.next;
        }
    }

    /*
    * 为链表添加节点,可以指定作游戏的孩子个数(nums)
    * */
    public void addNode(int nums){
        if(nums < 1){
            // 玩游戏的孩子数量不能小于1,否则没有进行下去的必要,直接抛出异常
            throw new RuntimeException("游戏人数需要>=1");
        }

        // 循环创建孩子节点,编号从1开始
        for (int i = 1; i <= nums; i++) {
            Boy curboy = First;// 记录当前位置
            Boy boy = new Boy(i);
            if(i == 1){
                First = boy;
                First.next = First;
                continue;
            }

            // 遍历找尾
            while(curboy.next != First){
                curboy = curboy.next;
            }

            boy.next = curboy.next;
            curboy.next = boy;
        }
    }

    public void show(){
        if(First == null){
            System.out.println("当前链表无元素,请添加元素后在尝试打印");
        }

        Boy cur = First;
        while(cur.next != First){
            System.out.print(cur.no+" -> ");
            cur = cur.next;
        }
        System.out.println(cur.no+" -> "+First.no);
    }
}

/*
* 节点类,代表作游戏的孩子
* */
class Boy{
    int no;
    Boy next;


    public Boy(int no) {
        this.no = no;
    }
}
